﻿// 604 动态中位数.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <queue>

using namespace std;

/*
http://oj.daimayuan.top/course/7/problem/495

中位数是按顺序排列的一组数据中居于中间位置的数。

现在依次给你 n个整数 a1,a2,…,an
（保证 n为奇数），你需要分别计算读入到第 1,3,5,…,n个数时，当前的中位数是多少。

输入格式
第一行一个整数 n。

接下来一行 n个整数 a1,a2,…,an。

输出格式
输出一行 (n+1)/2个整数，表示答案。

样例输入
9
1 2 3 4 5 6 7 8 9
样例输出
1 2 3 4 5
数据规模
对于 100%
 的数据，保证 1≤n≤105,1≤ai≤109。
*/

priority_queue<int, vector<int>, greater<int>> qg;
priority_queue<int, vector<int>, less<int>> ql;

int n;

int main()
{
	cin >> n;

	for (int i = 1; i <= n; i++) {
		int a; cin >> a;
		if ( qg.empty()|| a >= qg.top()) qg.push(a);
		else ql.push(a);

		while ((int)qg.size() - (int)ql.size() > 1 ) {
			int t = qg.top(); qg.pop();
			ql.push(t);
		}
		while ((int)ql.size() > (int)qg.size()) {
			int t = ql.top(); ql.pop();
			qg.push(t);
		}

		if (i % 2) {
			cout << qg.top() << endl;
		}
	}

	return 0;
}

 